package com.example.demo.tixiban;

/**
 * @author xujm
 * @version V2.4
 * 双链表反转
 * @since 2.4.0 2022/2/10 19:11
 */
public class List_双链表的反转 {


    public static class DoubleNode {
        int val;
        DoubleNode next;
        DoubleNode pre;
        DoubleNode(int x) { val = x; }
    }

    /**
     *  (1)
     *   null    a   ->  b   ->  c  ->  null
     *        <=    <=     <=
     *    pre    head    next
     *    pre = head.pre;
     *    next = head.next;
     *   (2)
     *    head.next = pre;
     *   null  <-  a    b   ->  c  ->  null
     *        <=    <=     <=
     *    pre    head  next
     *    (3)
     *    head.pre = next;(a => b)
     *    head = next;
     *   null  <-  a => b   ->  c  ->  null
     *              <=     <=
     *            pre  head
     *
     *    (4)        <-
     *   null  <-  a =>  b => c  ->  null
     *                    <=
     *            pre  head   next
     *                        head
     *      pre = head.pre;
     *      next = head.next;
     *      head.next = pre;
     *      head.pre = next;
     *      temp = head(记录一下 最后head为空时返回)
     *      head = next;
     *
     *    (4)        <-    <-
     *   null  <-  a =>  b => c => null
     *                   pre  head  next
     *                              head
     * @param head
     * @return
     */
    public static DoubleNode revese(DoubleNode head){

        DoubleNode pre = null;
        DoubleNode next = null;
        DoubleNode temp =null;
        while(head != null){
            pre = head.pre;
            next = head.next;
           head.next = pre;
           head.pre = next;
           temp = head;
           head = next;
        }
        return temp;
    }

    public static void main(String[] args) {

        DoubleNode node = new DoubleNode(1);
        node.pre=null;
        DoubleNode node2 = new DoubleNode(2);
        node2.pre=node;
        DoubleNode node3 = new DoubleNode(3);
        node3.pre=node2;
        node.next = node2;
        node2.next = node3;
        node3.next = null;
        DoubleNode revese = revese(node);
        System.out.println(revese.val);
    }


}
